package com.mlh.binarytree;

/**
 * @author 缪林辉
 * @date 2024/4/1 13:55
 * @DESCRIPTION
 */
// 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
// 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
// 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

// 思路一：用普通二叉树的共同祖先查找当然可以完成，但是有进一步提升的空间
// 思路二：利用二叉搜索树的特性，如果一个节点是q,p 的最近的共同祖先，该节点的值一定是在q和p的值的中间（是必定的，可以思考一下）
public class 二叉搜索树的最近公共祖先 {
    public TreeNode method1(TreeNode root, TreeNode p, TreeNode q) {
        return recursion(root,p,q);
    }

    //思路二的递归版本
    public TreeNode recursion(TreeNode node, TreeNode p, TreeNode q){
        if(node==null||p.val>=q.val&&node.val>=q.val&&node.val<=p.val||p.val<=q.val&&node.val>=p.val&&node.val<=q.val){
            return node;
        }
        //相对于普通二叉树，这样可以直接返回，为什么呢？因为这里我们直接找到就是他们的共同祖先
        //不需要通过向左树递归和向右树递归的返回值来判断，该节点是否是q,p 两节点的共同祖先
        //因此只要找到了，就可以直接返回就完事了，不需要继续递归了
        TreeNode left=recursion(node.left, p, q);
        if (left!=null){
            return left;
        }
        return recursion(node.right, p, q);
    }

    //思路二的迭代版本
    public TreeNode method2(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null){
            if(root.val>p.val&&root.val>q.val){
                root=root.left;
            }else if(root.val<p.val&&root.val<q.val){
                root=root.right;
            }else{
               break;
            }
        }
        return root;
    }

    public TreeNode recursionPractice(TreeNode node, TreeNode p, TreeNode q){
        if(node==null){
            return null;
        }
        if(node.val>=p.val&&node.val<=q.val||node.val>=q.val&&node.val<=p.val){
            return node;
        }
        TreeNode left = recursionPractice(node.left, p, q);
        return left!=null?left:recursionPractice(node.right,p,q);
    }
}
